/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: OR14 最长公共子序列
 * <a href="https://www.nowcoder.com/practice/c996bbb77dd447d681ec6907ccfb488a?tpId=182&tqId=34740&ru=/exam/oj">...</a>
 * User: DELL
 * Date: 2023-05-10
 * Time: 17:10
 */
public class LCS {

    /**
     * 解题思路: 动态规划
     * 状态定义: dp[i][j] = A 的前 i 个字符的字串和 B 的前 j 个字符的字串的最长公共子序列的长度
     * 状态转移: 当 A 的第 i 个字符 == B 的第 j 个字符:
     *         dp[i][j] = dp[i-1][j-1] + 1
     *         当 A 的第 i 个字符 != B 的第 j 个字符
     *         即最长的公共子串只有两种情况: 1. 不包括 A 的第 i 个字符 2. 不包括 B 的第 j 个字符
     *         dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])
     * 初始化: dp[0][j] = 0 && dp[i][0] = 0
     * 返回值: 返回右下角的值即可
     */
    public int findLCS(String A, int n, String B, int m) {
        //状态数组
        int[][] dp = new int[n+1][m+1];
        //不用初始化,创建的时候默认为0
        //状态转移
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[n][m];
    }
}